{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Level Sum of a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxLevelSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大层内元素和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根节点&nbsp;<code>root</code>。设根节点位于二叉树的第 <code>1</code> 层，而根节点的子节点位于第 <code>2</code> 层，依此类推。</p>\n",
    "\n",
    "<p>请返回层内元素之和 <strong>最大</strong> 的那几层（可能只有一层）的层号，并返回其中&nbsp;<strong>最小</strong> 的那个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/08/17/capture.jpeg\" style=\"height: 175px; width: 200px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,7,0,7,-8,null,null]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "第 1 层各元素之和为 1，\n",
    "第 2 层各元素之和为 7 + 0 = 7，\n",
    "第 3 层各元素之和为 7 + -8 = -1，\n",
    "所以我们返回第 2 层的层号，它的层内元素之和最大。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [989,null,10250,98693,-89388,null,null,null,-32127]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在<meta charset=\"UTF-8\" />&nbsp;<code>[1, 10<sup>4</sup>]</code>范围内<meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-level-sum-of-a-binary-tree](https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-level-sum-of-a-binary-tree](https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,7,0,7,-8,null,null]', '[989,null,10250,98693,-89388,null,null,null,-32127]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        queue = [root]\n",
    "        max_level = 1\n",
    "        max_sum = float('-inf')\n",
    "        level = 1\n",
    "\n",
    "        while queue:\n",
    "            level_sum = 0\n",
    "            next_level = []\n",
    "\n",
    "            for node in queue:\n",
    "                level_sum += node.val\n",
    "\n",
    "                if node.left:\n",
    "                    next_level.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level.append(node.right)\n",
    "\n",
    "            if level_sum > max_sum:\n",
    "                max_sum = level_sum\n",
    "                max_level = level\n",
    "\n",
    "            queue = next_level\n",
    "            level += 1\n",
    "\n",
    "        return max_level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        from queue import Queue\n",
    "        if root is None:\n",
    "            return\n",
    "        q = Queue()\n",
    "        cur_num = 1 \n",
    "        next_num = 0\n",
    "        num = 0\n",
    "        max_num = 0\n",
    "        index = 0\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            num = 0\n",
    "            while cur_num != 0:     \n",
    "                tmp = q.get()\n",
    "                if tmp.left is not None:\n",
    "                    q.put(tmp.left)\n",
    "                    tmp.left = None\n",
    "                    next_num = next_num + 1\n",
    "                if tmp.right is not None:\n",
    "                    q.put(tmp.right)\n",
    "                    tmp.right = None\n",
    "                    next_num = next_num + 1      \n",
    "                num = num + tmp.val\n",
    "                cur_num = cur_num - 1\n",
    "            cur_num = next_num\n",
    "            next_num = 0\n",
    "            index = index + 1\n",
    "            if num > max_num:\n",
    "                max_num = num\n",
    "                max_index = index\n",
    "        return max_index\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        cur_level = [root]\n",
    "        ans = 1\n",
    "        step = 1\n",
    "        maxval = root.val\n",
    "        while cur_level:\n",
    "            next_level = []\n",
    "            qq = []        \n",
    "            for i in cur_level:\n",
    "                if i.left:\n",
    "                    next_level.append(i.left)\n",
    "                    qq.append(i.left.val)\n",
    "                if i.right:\n",
    "                    next_level.append(i.right)\n",
    "                    qq.append(i.right.val)\n",
    "            q = sum(qq)\n",
    "            step += 1\n",
    "            if maxval<q:\n",
    "                maxval = q \n",
    "                ans = step\n",
    "            cur_level = next_level\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        currentLevelNodes = [root]\n",
    "        currentLevel = 1\n",
    "        maxiumLevelSum = -float(\"inf\")\n",
    "        level = 0\n",
    "        while currentLevelNodes:\n",
    "            nextLevelNodes = []\n",
    "            currentLevelSum = 0\n",
    "            for node in currentLevelNodes:\n",
    "                currentLevelSum += node.val\n",
    "                if node.left:\n",
    "                    nextLevelNodes.append(node.left)\n",
    "                if node.right:\n",
    "                    nextLevelNodes.append(node.right)\n",
    "            if currentLevelSum > maxiumLevelSum:\n",
    "                maxiumLevelSum = currentLevelSum\n",
    "                level = currentLevel\n",
    "            currentLevelNodes = nextLevelNodes\n",
    "            currentLevel += 1\n",
    "        return level\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        max_layer_num = 1\n",
    "        now_layer_num = 0\n",
    "        max_num = root.val\n",
    "        import collections\n",
    "        q = collections.deque()\n",
    "        q.appendleft(root)\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            num = 0\n",
    "            now_layer_num += 1\n",
    "            for _ in range(size):\n",
    "                cursor = q.pop()\n",
    "                num += cursor.val\n",
    "                if cursor.left:\n",
    "                    q.appendleft(cursor.left)\n",
    "                if cursor.right:\n",
    "                    q.appendleft(cursor.right)\n",
    "            if num > max_num:\n",
    "                max_num = num\n",
    "                max_layer_num = now_layer_num\n",
    "        return max_layer_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        if root==None: return 0\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        rs = []\n",
    "        while que:\n",
    "            s = []\n",
    "            for n in que:\n",
    "                s.append(n.val)\n",
    "            rs.append(sum(s))\n",
    "            nodes = []\n",
    "            while que:\n",
    "                node = que.popleft()\n",
    "                if node.left!=None: nodes.append(node.left)\n",
    "                if node.right!=None: nodes.append(node.right)\n",
    "            for node in nodes:\n",
    "                que.append(node)\n",
    "        maxs = max(rs)\n",
    "        return rs.index(maxs)+1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        source = collections.defaultdict(int)\n",
    "        def dfs(node,level):\n",
    "            if not node:\n",
    "                return\n",
    "            source[level] += node.val\n",
    "            dfs(node.left,level + 1)\n",
    "            dfs(node.right,level + 1)\n",
    "        dfs(root,1)\n",
    "        if not root:\n",
    "            return \n",
    "        return sorted(source.items(),key = lambda x:(-x[1],[0]))[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root):\n",
    "        all_path = collections.deque()\n",
    "        all_path.append([1, root])\n",
    "        all_sum = collections.defaultdict(int)\n",
    "\n",
    "        while all_path:\n",
    "            num, node = all_path.popleft()\n",
    "            all_sum[num] += node.val\n",
    "            if node.left:\n",
    "                all_path.append([num+1, node.left])\n",
    "            if node.right:\n",
    "                all_path.append([num+1, node.right])\n",
    "\n",
    "        return max(all_sum, key=lambda x: all_sum[x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        ret = 0\n",
    "        curlvl = 1\n",
    "        sm = float('-inf')\n",
    "        cur = [root]\n",
    "        while len(cur)>0:\n",
    "            ncur = []\n",
    "            tmpsm = 0\n",
    "            for c in cur:\n",
    "                tmpsm += c.val\n",
    "                if c.left!=None:\n",
    "                    ncur.append(c.left)\n",
    "                if c.right!=None:\n",
    "                    ncur.append(c.right)\n",
    "            if tmpsm>sm:\n",
    "                sm = tmpsm\n",
    "                ret = curlvl\n",
    "            curlvl += 1\n",
    "            cur = ncur\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        res = {}\n",
    "        temp = []\n",
    "        pre = 1\n",
    "        k = float(-inf)\n",
    "        queue = [(root,1)]\n",
    "        while queue:\n",
    "            node,level = queue.pop(0)\n",
    "            if not node:continue\n",
    "            if level != pre:\n",
    "                if sum(temp) not in res:\n",
    "                    res[sum(temp)] = pre\n",
    "                k = max(k,sum(temp))\n",
    "                temp = [node.val]\n",
    "            else:\n",
    "                temp.append(node.val)\n",
    "            pre = level\n",
    "            queue.append((node.left,level+1))\n",
    "            queue.append((node.right,level+1))\n",
    "        if sum(temp) not in res:\n",
    "            res[sum(temp)] = pre\n",
    "            k = max(k,sum(temp))\n",
    "        return res[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        if root == None:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        print(queue)\n",
    "        result = []\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for i in range(len(queue)):\n",
    "                temp_node = queue.pop(0)\n",
    "                temp.append(temp_node.val)\n",
    "                if temp_node.left:\n",
    "                    queue.append(temp_node.left)\n",
    "                if temp_node.right:\n",
    "                    queue.append(temp_node.right)\n",
    "            result.append(temp)\n",
    "        val = []\n",
    "        for i in range(len(result)):\n",
    "            val.append(sum(result[i]))\n",
    "        max_val = max(val)\n",
    "        for i in range(len(val)):\n",
    "            if(val[i] == max_val):\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: TreeNode) -> int:\n",
    "        q = queue.Queue()\n",
    "        sumn = -float(\"inf\") \n",
    "        res = []\n",
    "        q.put(root)\n",
    "        q.put(None)\n",
    "        cnt = 1\n",
    "        while not q.empty():\n",
    "            tmp_sum = 0\n",
    "            node = q.get()\n",
    "            if not node:\n",
    "                return res[0]\n",
    "            while node:\n",
    "                tmp_sum += node.val\n",
    "                if node.left:\n",
    "                    q.put(node.left)\n",
    "                if node.right:\n",
    "                    q.put(node.right)\n",
    "                node = q.get()\n",
    "            q.put(None)\n",
    "            if tmp_sum > sumn:\n",
    "                res = [cnt]\n",
    "                sumn = tmp_sum\n",
    "            elif tmp_sum == sumn:\n",
    "                res.append(cnt)\n",
    "            # print(tmp_sum)\n",
    "            cnt += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, node, level):\n",
    "        if node is None:\n",
    "            return\n",
    "        if level == len(self.sum) + 1:\n",
    "            self.sum.append(node.val)\n",
    "        else:\n",
    "            self.sum[level-1] += node.val\n",
    "        self.traverse(node.left, level + 1)\n",
    "        self.traverse(node.right, level + 1)\n",
    "        \n",
    "\n",
    "    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n",
    "        self.sum = []\n",
    "        self.traverse(root, 1)\n",
    "        return self.sum.index(max(self.sum)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n",
    "        import collections\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        ret = float('-inf')\n",
    "        ret_level = 0\n",
    "        level = 1\n",
    "        while q:\n",
    "            level_length = len(q)\n",
    "            curSum = 0\n",
    "            for _ in range(level_length):\n",
    "                temp = q.popleft()\n",
    "                curSum += temp.val\n",
    "                if temp.left:\n",
    "                    q.append(temp.left)\n",
    "                if temp.right:    \n",
    "                    q.append(temp.right)\n",
    "            if curSum > ret:\n",
    "                ret = curSum\n",
    "                ret_level = level\n",
    "            level += 1\n",
    "        return ret_level\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, t: Optional[TreeNode]) -> int:\n",
    "        v, x = -inf, 0\n",
    "        q = [t]\n",
    "        j = 1\n",
    "        while q:\n",
    "            p = []\n",
    "            c = 0\n",
    "            for i in q:\n",
    "                d = i\n",
    "                c += d.val\n",
    "                if d.left: p.append(d.left)\n",
    "                if d.right: p.append(d.right)\n",
    "            q = p\n",
    "            if c > v:\n",
    "                v, x = c, j\n",
    "            j += 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n",
    "        nodes = [root]\n",
    "        res, max_v, depth = 1, -inf, 0\n",
    "        while nodes:\n",
    "            depth += 1\n",
    "            v = 0\n",
    "            temp = []\n",
    "            for node in nodes:\n",
    "                v += node.val\n",
    "                if node.left: temp.append(node.left)\n",
    "                if node.right: temp.append(node.right)\n",
    "            if v > max_v:\n",
    "                max_v = v\n",
    "                res = depth\n",
    "            nodes = temp\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = [root]\n",
    "        max_sum = float('-inf')\n",
    "        vals = []\n",
    "\n",
    "        while queue != []:\n",
    "            pre = []\n",
    "            temp = []\n",
    "            while queue != []:\n",
    "                node = queue.pop(0)\n",
    "                pre.append(node.val)\n",
    "                if node.left is not None:\n",
    "                    temp.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    temp.append(node.right)\n",
    "            vals.append(sum(pre))\n",
    "            queue = temp\n",
    "\n",
    "        return vals.index(max(vals)) + 1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n",
    "        max_depth = -1\n",
    "        sum_val = []\n",
    "        q = [[root, 0]]\n",
    "        while q:\n",
    "            node, depth = q.pop()\n",
    "            if depth > max_depth:\n",
    "                sum_val.append(node.val)\n",
    "                max_depth = depth\n",
    "            else:\n",
    "                sum_val[depth] += node.val\n",
    "            if node.left:\n",
    "                q.append([node.left, depth+1])\n",
    "            if node.right:\n",
    "                q.append([node.right, depth+1])\n",
    "        return sum_val.index(max(sum_val)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n",
    "        to_search = [root]\n",
    "        max_level = []\n",
    "        max_sum = None\n",
    "        level = 1\n",
    "        while to_search:\n",
    "            tmp = []\n",
    "            level_sum = 0\n",
    "            for node in to_search:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "                level_sum += node.val\n",
    "            if max_sum is None:\n",
    "                max_sum = level_sum\n",
    "                max_level.append(level)\n",
    "            else:\n",
    "                if level_sum > max_sum:\n",
    "                    max_sum = level_sum\n",
    "                    max_level = [level]\n",
    "                elif level_sum == max_sum:\n",
    "                    max_level.append(level)\n",
    "            to_search = tmp\n",
    "            level += 1\n",
    "        return min(max_level)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n",
    "        # bfs\n",
    "        max_sum = None\n",
    "        q = [root]\n",
    "        ans = None\n",
    "        index = 1\n",
    "        while q:\n",
    "            temp = q\n",
    "            q = []\n",
    "            temp_sum = 0\n",
    "            for node in temp:\n",
    "                temp_sum += node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            if max_sum is None or max_sum<temp_sum:\n",
    "                max_sum = temp_sum\n",
    "                ans = index\n",
    "            index += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
